package com.algorithm.dac;

public class DivideAndConquer {
    public static void main(String[] args) {
        hanoiTower(3,'A','B','C');

    }

    /**
     * 分治算法解决：汉罗塔问题,将A柱上的所有盘移动到C柱上
     * @param num
     * @param a 起始塔
     * @param b 辅助塔
     * @param c 目标塔
     */
    public static void hanoiTower(int num,char a,char b,char c){
        if(num == 1){
            System.out.println("第1个盘从 "+a+"->"+c);
        }else {
            //n>=2的情况，将所有盘都看做是两个盘，即最底下的盘和上面的盘
            //1. 先把最上面的盘 A - B
            hanoiTower(num-1,a,c,b);
            //2. 把底下盘 A - C
            System.out.println("第"+num+"个盘从 "+a+"->"+c);
            //3. 再将B塔的所有盘 B - C
            hanoiTower(num-1,b,a,c);
        }
    }
}
